#include <vector>

using namespace std;

class Solution {
public:
    int ways(vector<string>& pizza, int k) {
        k--;
        int height = pizza.size();
        int width = pizza[0].size();
        vector<vector<vector<int>>> dp(height, vector<vector<int>>(width, vector<int>(k + 1)));
        vector<vector<int>> sum(height, vector<int>(width));
        if (pizza[height - 1][width - 1] == 'A') {
            sum[height - 1][width - 1] = 1;
        }
        for (int i = width - 2; i >= 0; i--) {
            sum[height - 1][i] += sum[height - 1][i + 1];
            if (pizza[height - 1][i] == 'A') {
                sum[height - 1][i]++;
            }
        }
        for (int i = height - 2; i >= 0; i--) {
            sum[i][width - 1] += sum[i + 1][width - 1];
            if (pizza[i][width - 1] == 'A') {
                sum[i][width - 1]++;
            }
        }
        for (int i = height - 2; i >= 0; i--) {
            for (int j = width - 2; j >= 0; j--) {
                sum[i][j] += sum[i + 1][j] + sum[i][j + 1] - sum[i + 1][j + 1];
                if (pizza[i][j] == 'A') {
                    sum[i][j]++;
                }
            }
        }
        dp[0][0][0] = 1;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                for (int l = 0; l < k; l++) {
                    for (int m = i; m < height - 1; m++) {
                        if (sum[m + 1][j] == 0 || sum[i][j] - sum[m + 1][j] == 0) {
                            continue;
                        }
                        dp[m + 1][j][l + 1] += dp[i][j][l];
                        dp[m + 1][j][l + 1] %= (int) 1e9 + 7;
                    }
                    for (int m = j; m < width - 1; m++) {
                        if (sum[i][m + 1] == 0 || sum[i][j] - sum[i][m + 1] == 0) {
                            continue;
                        }
                        dp[i][m + 1][l + 1] += dp[i][j][l];
                        dp[i][m + 1][l + 1] %= (int) 1e9 + 7;
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < height; i++) {
            for (int j = 0; j < width; j++) {
                ans += dp[i][j][k];
                ans %= (int) 1e9 + 7;
            }
        }
        return ans;
    }
};